package datastructure.search;

/**
 * 插值查找
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-26
 */
public class InsertValueSearch {

    private static int COUNT = 0;

    public static void main(String[] args) {
        int[] array = new int[100];
        for (int i = 0; i <= 99; i++) {
            array[i] = i + 1;
        }
        int index = insertValueSearch(array, 0, array.length - 1, 88);
        if (index == -1) {
            System.out.println("没查找到~~~~");
        } else {
            System.out.println("找到，下标为：" + index);
        }
    }

    /**
     * 插值查找
     * 数组也应该有序
     *
     * @param array   查找数据
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 需要查找的数
     * @return 下标
     */
    private static int insertValueSearch(int[] array, int left, int right, int findVal) {
        System.out.println("二分次数："+ ++COUNT);
        // findVal < array[left] || findVal > array[right] 必须要 防止后面mid可能越界
        if (left > right || findVal < array[left] || findVal > array[right]) {
            return -1;
        }
        // 求出mid 公式
        int mid = left + (right - left) * (findVal - array[left]) / (array[right] - array[left]);
        int midVal = array[mid];
        if (findVal > midVal) {
            return insertValueSearch(array, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return insertValueSearch(array, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

}
